package leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode-hot100: 螺旋矩阵
 * 测试链接: https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给定一个m行n列的矩阵，按顺时针螺旋顺序返回矩阵中所有的元素
 */
public class SpiralMatrix {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList();
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0, j = 0;
        //定义方向数组，按右下左上的顺序走(顺时针)
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int index = 0;
        for(int k = 0; k < m * n; k++){
            ans.add(matrix[i][j]);
            matrix[i][j] = Integer.MIN_VALUE;
            int x = dir[index][0] + i;
            int y = dir[index][1] + j;
            //如果到达边界(矩阵边界、已经访问过的元素也是边界)，调转下一个方向
            if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == Integer.MIN_VALUE){
                //取模来控制螺旋方向(右->下->左->上)
                index = (index + 1) % 4;
            }
            //改变当前坐标
            i += dir[index][0];
            j += dir[index][1];
        }
        return ans;
    }
}
